package B.链表;

import com.sun.org.apache.xml.internal.security.utils.HelperNodeList;

public class _21_合并两个有序链表 {
    /**
     * 自解：过于繁琐 而且第二个链表连续小时情况没考虑
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null){
            return l2;
        }else if (l2 == null){
            return l1;
        }else {
            ListNode sential = new ListNode(0);

            ListNode p1 = new ListNode();
            ListNode p2 = new ListNode();

            //p1转至小开头的链表
            if (l1.val <= l2.val){
                p1= l1;
                p2= l2;
                sential.next = l1;

            }else {
                p1= l2;
                p2= l1;
                sential.next = l2;
            }

            ListNode temp= new ListNode();
            while (p1.next != null && p2!=null){
                if (p1.next.val <= p2.val){
                    p1 = p1.next;
                }else {
                    temp = p2.next;
                    while (temp.val <= p1.next.val){
                        temp = temp.next;

                    }

                    p2.next=p1.next;
                    p1.next = p2;
                    p1 = p2.next;
                    p2 = temp;

                }
            }

            if (p1.next == null){
                p1.next =p2;
            }

            return sential.next;


        }


    }

    /**
     * 迭代法维护一个 prev 指针，我们需要做的是调整它的 next 指针
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {

        ListNode sential = new ListNode(0);
        ListNode cur = sential;

        while (l1 != null && l2 != null){
            if (l1.val <= l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else {
                cur.next = l2;
                l2 = l2.next;
            }

            cur = cur.next;
        }

        //直接将没完的合并进入
        cur.next = l1==null?l2:l1;

        return sential.next;


    }
}
